package 力扣.动态规划;
//给定一个非负整数数组，a1, a2, ..., an, 和一个目标数，S。现在你有两个符号 + 和 -。
// 对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。
//
//返回可以使最终数组和为目标数 S 的所有添加符号的方法数。

public class 目标和 {
    public static void main(String[] args) {
        int[] nums={1,1,1,1,1};
        int i = findTargetSumWays(nums, 3);
        System.out.println(i);
    }
    public static int findTargetSumWays(int[] nums, int S) {
//         sum(P) - sum(N) = target
//sum(P) + sum(N) + sum(P) - sum(N) = target + sum(P) + sum(N)
//         2 * sum(P) = target + sum(nums)
        int sum=0;
        for (int i = 0; i < nums.length; i++) {
            sum+=nums[i];
        }
        int m=sum+S;
        if (m%2!=0 || sum<S)
            return 0;
        else
            m=m/2;
        int[] dp = new int[m + 1];
        dp[0]=1;
        for (int num: nums) {
            for (int i = m; i >=num ; i--) {
                dp[i]+=dp[i-num];
            }
        }
        return dp[m];
    }
}
